package org.anno.chunkdb;

import com.google.common.base.Preconditions;

import it.unimi.dsi.fastutil.ints.AbstractIntList;

/**
 * Stores an array of unsigned integers bit-encoded.
 */
public class IntArray extends AbstractIntList {

  private final int bitsPerInt;
  private final byte[] data;

  public IntArray(int bitsPerInt, byte[] data) {
    this.bitsPerInt = bitsPerInt;
    this.data = data;
  }

  @Override
  public int size() {
    return 8 * data.length / bitsPerInt;
  }

  @Override
  public int getInt(int i) {
    int bitIndex = i * bitsPerInt;
    int dataIndex = bitIndex >> 3;
    bitIndex &= 7;
    int result = 0;
    int needBits = bitsPerInt;
    while (true) {
      int availableBitsHere = 8 - bitIndex;
      int dataBits = ((int) data[dataIndex]) & ((1 << availableBitsHere) - 1);
      int extraBits = availableBitsHere - needBits;
      if (extraBits >= 0) {
        return (result << needBits) | (dataBits >> extraBits);
      }
      result = (result << availableBitsHere) | dataBits;
      needBits -= availableBitsHere;
      bitIndex = 0;
      dataIndex += 1;
    }
  }

  public static IntArray build(int[] ints) {
    int max = 0;
    for (int i : ints) {
      Preconditions.checkArgument(i >= 0);
      if (i > max) {
        max = i;
      }
    }
    int bitsPerInt = 32 - Integer.numberOfLeadingZeros(max);
    byte[] data = new byte[(bitsPerInt * ints.length + 7) / 8];

    int dataIndex = 0;
    int freeBitsAtDataIndex = 8;
    for (int toEncode : ints) {
      int bitsToEncode = bitsPerInt;
      int mask = (1 << bitsPerInt) - 1;
      while (bitsToEncode > freeBitsAtDataIndex) {
        data[dataIndex++] |= (mask & toEncode) >> (bitsToEncode - freeBitsAtDataIndex);
        bitsToEncode -= freeBitsAtDataIndex;
        mask >>>= freeBitsAtDataIndex;
        freeBitsAtDataIndex = 8;
      }
      freeBitsAtDataIndex -= bitsToEncode;
      data[dataIndex] |= (mask & toEncode) << freeBitsAtDataIndex;
    }
    return new IntArray(bitsPerInt, data);
  }
}
